package com.fanshuai.algorithms.slidewindow;

import java.util.*;

/**
 * 滑动窗口算法 伪代码框架
 * String s, t;
 * int left = 0, right = 0; //滑动窗口左右指针初始化为0
 * String res = s;  //问题解 滑动窗口问题一般为求满足某种条件的子串
 *
 * while(right < s.size()) { //滑动窗口遍历完
 *     window.add(s.charAt(right)); //更新滑动窗口统计信息
 *     right++;
 *
 *     while(window 符合要求) {
 *          res = min(res, window) //更新最小子串
 *          window.remove(s[left]) //移动滑动窗口左指针
 *          left++
 *     }
 * }
 */
public class SlideWindow {
    /**
     * 最小覆盖子串
     * 给你一个字符串S, 字符串T，在S里面找出：包含T所有字母的最小子串
     */
    public static String minWindow(String s, String t) {
        int left = 0, right = 0;
        Map<Character, Integer> window = new HashMap<>();
        Set<Character> needs = new HashSet<>();
        for (Character c : t.toCharArray()) {
            needs.add(c);
        }
        int startIndex = -1, len = s.length() + 1;

        while (right < s.length()) {
            char rightChar = s.charAt(right);
            if (needs.contains(rightChar)) {
                addCount(window, s.charAt(right));
            }
            right++;

            while (window.size() == needs.size()) {
                if (right - left < len) {
                    startIndex = left;
                    len = right - left;
                }

                if (needs.contains(s.charAt(left))) {
                    delCount(window, s.charAt(left));
                }
                left++;
            }
        }

        if (len == s.length() + 1) {
            return null;
        } else {
            return s.substring(startIndex, startIndex + len);
        }
    }

    private static void addCount(Map<Character, Integer> map, Character c) {
        if (map.containsKey(c)) {
            map.put(c, map.get(c) + 1);
        } else {
            map.put(c, 1);
        }
    }

    private static void delCount(Map<Character, Integer> map, Character c) {
        Integer count = map.get(c);
        if (count != null) {
            if (count.equals(1)) {
                map.remove(c);
            } else {
                map.put(c, count - 1);
            }
        }
    }

    private static boolean mapEquals(Map<Character, Integer> need, Map<Character, Integer> window) {
        if (null == need && null == window) {
            return true;
        } else {
            if (null == need || null == window) {
                return false;
            }
            if (need.size() != window.size()) {
                return false;
            }
            for (Character key : need.keySet()) {
                if (!need.get(key).equals(window.get(key))) {
                    return false;
                }
            }

            return true;
        }
    }

    /**
     * 找到字符串中所有字母异位词
     * 给定字符串s和字符串p，找出S中所有是p的异位字符的子串, 返回开始索引
     * 字母异位词指字母相同，排列不同的字符串
     */
    public static List<Integer> findAnagrams(String s, String p) {
        if (null == s || null == p) {
            return new ArrayList<>();
        }

        int left = 0, right = 0;
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (Character c : p.toCharArray()) {
            addCount(need, c);
        }

        List<Integer> indexs = new ArrayList<>();

        while (right < s.length()) {
            char rightChar = s.charAt(right);
            if (need.containsKey(rightChar)) {
                addCount(window, rightChar);
            }
            right++;

            while (right - left == p.length()) {
                if (mapEquals(need, window)) {
                    indexs.add(left);
                }

                char leftChar = s.charAt(left);
                if (need.containsKey(leftChar)) {
                    delCount(window, leftChar);
                }
                left++;
            }
        }

        return indexs;
    }

    /**
     * 无重复字符的最长子串
     */
    public static String longestUniqSubString(String s) {
        int left = 0, right = 0;
        Map<Character, Integer> window = new HashMap<>();
        int start = -1, len = Integer.MIN_VALUE;

        while (right < s.length()) {
            char ch = s.charAt(right);
            addCount(window, ch);
            right++;

            while (window.get(ch) > 1) {
                char ch2 = s.charAt(left);
                delCount(window, ch2);
                left++;
            }

            if (right - left > len) {
                len = right - left;
                start = left;
            }
        }

        if (len == Integer.MAX_VALUE) {
            return null;
        }
        return s.substring(start, start + len);
    }

    public static void main(String[] args) {
        String s = "asbxcfghfgaxcbrhdg";
        String s2 = "abodecodebanc";
        String t = "abc";

        System.out.println(minWindow(s, t));
        System.out.println(minWindow(s2, t));

        String s3 = "cbaebabacdabc";
        String p = "abc";

        System.out.println(findAnagrams(s3, p));

        String s4 = "abcabdcbbaedc";
        System.out.println(longestUniqSubString(s4));
    }
}
